package com.leetcode.dfs;

import java.util.*;

/**
 * 回溯思路
 */
public class Leetcode131 {
    List<List<String>> res = new LinkedList<>();

    public List<List<String>> partition(String s) {
        if (s == null) {
            return res;
        }
        LinkedList<String> trace = new LinkedList<>();
        int len = s.length();
        backtrace(s, 0, len, trace);
        return res;
    }

    private void backtrace(String s, int index, int len, LinkedList<String> trace) {
        if (index == len) {
            res.add(new ArrayList<>(trace));
        }

        for (int i = index; i < len; i++) {
            if (!isTrue(s, index, i)) {
                continue;
            }
            trace.add(s.substring(index, i + 1));
            backtrace(s, i + 1, len, trace);
            trace.removeLast();
        }
    }

    private boolean isTrue(String s, int i, int j) {
        String subStr = s.substring(i, j + 1);
        int l = 0, r = subStr.length() - 1;
        while (l < r) {
            if (subStr.charAt(l) == subStr.charAt(r)) {
                l++;
                r--;
            } else {
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        String s = "aab";
        System.out.println(new Leetcode131().partition(s));
    }
}
